#include <bits/stdc++.h>

using namespace std;




struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//根据vector值构建二叉树
TreeNode * gou(vector<int> num){
    if(num.size()==0) return nullptr;
    TreeNode *root=new TreeNode(num[0]);
    queue<TreeNode*> s;
    s.push(root);
    int index=1,len=num.size();
    while(!s.empty()&&index<len){
        TreeNode *p=nullptr,*q=nullptr;
        p=new TreeNode(num[index++]);
        if(index<len) q=new TreeNode(num[index++]);
        TreeNode *r=s.front();s.pop();
        r->left=p;r->right=q;
        s.push(p),s.push(q);
    }
    return root;
}


class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

class Solution {
    unordered_map<Node*,Node*> mp;
public:
    Node* copyRandomList(Node* head) {
        mp.clear();
        if(nullptr==head) return nullptr;
        Node *p=new Node(head->val),*q=head->next;
        mp.insert(make_pair(head,p));
        while(q){
            p->next=new Node(q->val);
            p=p->next;
            mp.insert(make_pair(q,p));
            q=q->next;
        }   
        p=head,q=mp[head];
        while(p){   
            if(p->random){
                q->random=mp[p->random];
            }
            q=q->next;
            p=p->next;
        }
        return mp[head];
    }
};









int main(){




    return 0;
}